Skip to main content

Intersection of Two Sorted Linked Lists

Problem​

Given two linked lists sorted in increasing order, create a new linked list representing the intersection of the two linked lists. The new linked list should be made without changing the original lists.

Note: The elements of the linked list are not necessarily distinct.

Examples​

Example 1:

Input:
LinkedList1 = 1->2->3->4->6
LinkedList2 = 2->4->6->8
Output:
2 4 6
Explanation: For the given two linked list, 2, 4 and 6 are the elements in the intersection.

Example 2:

Input:
LinkedList1 = 10->20->40->50
LinkedList2 = 15->40
Output:
40

Your Task​

You don't have to take any input or print anything. Your task is to complete the function findIntersection(), which will take the head of both of the linked lists as input and should find the intersection of the two linked lists and add all the elements in the intersection to the third linked list and return the head of the third linked list.

Expected Time Complexity: O(n+m)O(n + m)
Expected Auxiliary Space: O(n+m)O(n + m)

Note: n, m are the sizes of the respective linked lists.

Constraints​

  • 1≤sizeoflinkedlists≤50001 ≤ size of linked lists ≤ 5000
  • 1≤Datainlinkedlistnodes≤1041 ≤ Data in linked list nodes ≤ 10^4

Solution​

Intuition & Approach​

To find the intersection of two sorted linked lists, we can iterate through both lists simultaneously. By comparing the elements at each step, we can identify common elements and construct a new linked list to represent the intersection. This process allows us to efficiently determine which elements are present in both lists without altering the original structures.

Implementation​

class ListNode:
def __init__(self, x):
self.data = x
self.next = None

class Solution:
def findIntersection(self, head1, head2):
intersection = ListNode(0) # dummy node
tail = intersection

while head1 and head2:
if head1.data == head2.data:
tail.next = ListNode(head1.data)
tail = tail.next
head1 = head1.next
head2 = head2.next
elif head1.data < head2.data:
head1 = head1.next
else:
head2 = head2.next

return intersection.next

Time Complexity: O(n+m)O(n + m)
Auxiliary Space: O(n+m)O(n + m)

References​